package tree.threadedbinary;


/**
 * 线索化二叉树
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {

        //测试
        //创建一个二叉树
        ThreadBinaryTree binaryTree = new ThreadBinaryTree();
        //创建需要的节点
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "林冲5");
        HeroNode node6 = new HeroNode(6, "林冲6");
        HeroNode node7 = new HeroNode(7, "林冲7");


        //手动创建二叉树
        root.setLeft(node2);
        node2.setLeft(node4);
        node2.setRight(node5);
        root.setRight(node3);
        node3.setLeft(node6);
        node3.setRight(node7);

        binaryTree.setRoot(root);
        binaryTree.inficOrder();
        binaryTree.threadedNodes();

        //测试
        HeroNode left = node4.getRight();

        System.out.println(left);
    }
}

//创建二叉树
//定义一个二叉树
class ThreadBinaryTree{
    private HeroNode root;
    //为了实现线索化，需要创建一个当前节点的前驱节点的指针
    //在进行线索化的时候，pre总是保留前一个节点
    private HeroNode pre = null;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void threadedNodes(){
        this.threadedNodes(root);
    }

    //中序线索化

    /**
     *
     * @param node 当前需要线索化的节点
     */
    public void threadedNodes(HeroNode node){
        //判断该节点是不是为空
        if(node == null){
            return;
        }

        //先线索化左子树
        threadedNodes(node.getLeft());

        //线索化当前节点
        //先处理当前节点的前驱节点
        if(node.getLeft() == null){
            //让当前节点的左指针指向前驱节点
            node.setLeft(pre);
            //修改当前节点左指针的类型
            node.setLeftType(1);
        }

        //处理后继节点
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        //线索化右子树
        threadedNodes(node.getRight());
    }

    //前序遍历
    public void preOrder(){
        if(this.root !=null){
            this.root.preOrder();
        }else{
            System.out.println("当前二叉树为空");
        }
    }

    //中序遍历
    public void inficOrder(){
        if(this.root !=null){
            this.root.inficOrder();
        }else {
            System.out.println("当前二叉树为空");
        }
    }

    //后续遍历
    public void postOrder(){
        if(this.root !=null){
            this.root.postOrder();
        }else {
            System.out.println("当前二叉树为空");
        }
    }

    //删除节点
    public void delNode(int no){
        if(root !=null){
            if(root.getNo() ==  no){
                root = null;
            }else{
                root.delNode(no);
            }
        }else{
            System.out.println("节点为空，不能删除");
        }
    }

}



//创建节点
class HeroNode {
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    //定义leftType == 0 那么指向的是左子树，如果是1，表示指向前驱节点
    //rightType ==1 ,那么表示指向后继节点
    private int leftType;
    private int rightType;



    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //删除节点
    public void delNode(int no){
        if(this.left !=null && this.left.no == no){
            this.left = null;
            return;
        }
        if(this.right !=null && this.right.no == no){
            this.right = null;
            return;
        }
        if(this.left != null){
            this.left.delNode(no);
        }
        if(this.right != null){
            this.right.delNode(no);
        }
    }

    //节点的方法
    //前序遍历的方法
    public void preOrder(){
        System.out.println(this);  //先输出父节点
        //递归左子树
        if(this.left !=null){
            this.left.preOrder();
        }
        //递归向右子树
        if(this.right !=null){
            this.right.preOrder();
        }
    }

    //中序遍历
    public void inficOrder(){
        //递归向左子树递归
        if(this.left !=null){
            this.left.inficOrder();
        }
        //输出当前节点
        System.out.println(this);

        //递归向右子树递归
        if(this.right !=null){
            this.right.inficOrder();
        }
    }

    //后序遍历
    public void postOrder(){
        if(this.left !=null){
            this.left.postOrder();
        }
        if(this.right !=null){
            this.right.postOrder();
        }
        System.out.println(this);
    }
}
